package cn.demoncat.util.lang.entity.data;

/**
 * 双向循环链表
 * 
 * @author 延晓磊
 *
 * @since 2020年6月27日
 */
public class DoubleCircleLinkedList<E> extends DoubleLinkedList<E>{
 
	/**
	 * 判断是否为循环链表
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月28日
	 */
	@Override
	public boolean isCircle() {
		return false;
	}
	
	/**
	 * 添加到尾部
	 * 
	 * @param e
	 * 
	 * @author 延晓磊
	 * @return 
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public DoubleCircleLinkedList<E> add(E e) {
		if (last == null) {
			// 首次添加
			last = new LinkedNode<>(e, null, null);
			first = last;
			// 双向、循环链表
			first.setNext(last);
		} else {
			// 链式添加到末尾，循环关联头节点
			last.setNext(new LinkedNode<>(e, first, last));
			// 尾节点后移
			last = last.getNext();
		}
		first.setPre(last);
		// 计数
		size ++;
		return this;
	}
	
	/**
	 * 添加到头部
	 * 
	 * @param e
	 * 
	 * @author 延晓磊
	 * @return 
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public DoubleCircleLinkedList<E> first(E e) {
		if (first == null) {
			// 首次添加
			first = new LinkedNode<>(e, null, null);
			last = first;
			// 双向、循环链表
			first.setNext(last);
			first.setPre(last);
		} else {
			// 链式添加到头部，循环关联尾节点
			first.setPre(new LinkedNode<>(e, first, last));
			// 头节点前移
			first = first.getPre();
			last.setNext(first);
		}
		// 计数
		size ++;
		return this;
	}
	
	/**
	 * 插入
	 * 
	 * @param index 索引
	 * @param e
	 * 
	 * @throws RuntimeException 索引越界：index < 0 || index > size
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public void insert(int index, E e) {
		// 索引越界：小于size == 插入，等于size == 添加
		if (index < 0 || index > size) {
			throw LinkedList.INDEX_EX;
		}
		if (index == 0) {
			// 头部插入（处理first+last的指向）
			first(e);
		} else if (index == size) {
			// 尾部插入（处理first+last的指向）
			add(e);
		} else {
			// 找到索引位当前节点
			LinkedNode<E> node = first;
			for (int i = 0; i < index; i++) {
				node = node.getNext();
			}
			// 链式插入：新节点的next == 当前节点，当前节点的pre == 新节点；新节点的pre == 当前节点的pre，上一个节点的next == 新节点
			LinkedNode<E> newNode = new LinkedNode<>(e, node, node.getPre());
			node.getPre().setNext(newNode);
			node.setPre(newNode);
			// 计数
			size ++;
		}
	}
	
	/**
	 * 获取
	 * 
	 * @param index 索引，越界时循环取模
	 * @return
	 * 
	 * @throws RuntimeException 索引越界：size == 0
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public E get(int index) {
		// 链表为空
		if (isEmpty()) {
			throw LinkedList.INDEX_EX;
		}
		// 双向遍历
		LinkedNode<E> node;
		if (index >= 0) {
			// 正向（循环取模计数）
			node = first;
			for (int i = 0; i < index % size; i++) {
				node = node.getNext();
			}
		} else {
			// 反向（循环取模计数）
			node = last;
			for (int i = 0; i < -(1+index) % size; i++) {
				node = node.getPre();
			}
		}
		// 获取数据
		return node.getData();
	}
	
	/**
	 * 修改
	 * 
	 * @param index 索引，越界时循环取模
	 * @param e		索引原数据
	 * 
	 * @throws RuntimeException 索引越界：size == 0
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public E set(int index, E e) {
		// 链表为空
		if (isEmpty()) {
			throw LinkedList.INDEX_EX;
		}
		// 双向遍历
		LinkedNode<E> node;
		if (index >= 0) {
			// 正向（循环取模计数）
			node = first;
			for (int i = 0; i < index % size; i++) {
				node = node.getNext();
			}
		} else {
			// 反向（循环取模计数）
			node = last;
			for (int i = 0; i < -(1+index) % size; i++) {
				node = node.getPre();
			}
		}
		// 节点原数据
		E old = node.getData();
		// 修改节点数据
		node.setData(e);
		return old;
	}
	
	/**
	 * 删除
	 * 
	 * @param index 索引，越界时循环取模
	 * 
	 * @return 索引原数据
	 * 
	 * @throws RuntimeException 索引越界：size == 0
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public E del(int index) {
		// 链表为空
		if (isEmpty()) {
			throw LinkedList.INDEX_EX;
		}
		// 循环取模
		if (index > size -1) {
			index = index % size;
		}else if (index < 0) {
			index = size + index % size;
		}
		// 删除节点
		E old;
		if (index == 0) {
			// 头节点原数据
			old = first.getData();
			// 头部删除（处理first+last的指向）
			if (size() == 1) {
				// 单个节点
				first = null;
				last = null;
			} else {
				// 头节点后移（原头节点失去引用）
				first = first.getNext();
				first.setPre(last);
				last.setNext(first);
				if (size() == 2) {
					last.setPre(first);
				}
			}
		} else {
			// 找到索引位当前节点
			LinkedNode<E> node = first;
			for (int i = 0; i < index; i++) {
				node = node.getNext();
			}
			// 节点原数据
			old = node.getData();
			// 链式删除：上一个节点的next == 当前节点的next，下一个节点的pre == 当前节点的pre，当前节点退出链表（由垃圾回收机制删除）
			node.getPre().setNext(node.getNext());
			node.getNext().setPre(node.getPre());
			// 尾部删除（处理first+last的指向）
			if (index == size() - 1) {
				// 尾节点前移
				last = node.getPre();
			}
		}
		// 计数
		size --;
		return old;
	}
	
	/**
	 * 删除
	 * 
	 * @param node	节点
	 * 
	 * @return 节点数据，null表示未找到/节点数据为null
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public E del(LinkedNode<E> node) {
		if (node == null || isEmpty()) {
			return null;
		}
		// 头节点
		if (first == node) {
			if (size == 1) {
				// 单个节点
				first = null;
				last = null;
			}else {
				// 头节点后移（原头节点失去引用）
				first = first.getNext();
				first.setPre(last);
				last.setNext(first);
				if (size() == 2) {
					last.setPre(first);
				}
			}
		}else {
			// 找到当前节点
			LinkedNode<E> curr = first.getNext();
			while (true) {
				// 找到节点
				if (curr == node) {
					// 链式删除：上一个节点的next == 当前节点的next，下一个节点的pre == 当前节点的pre，当前节点退出链表（由垃圾回收机制删除）
					curr.getPre().setNext(curr.getNext());
					curr.getNext().setPre(curr.getPre());
					// 尾部删除（处理first+last的指向）
					if (curr.getNext() == first) {
						// 尾节点前移
						last = node.getPre();
					}
					break;
				}else {
					// 继续遍历
					curr = curr.getNext();
					// 遍历到末尾
					if (curr == first) {
						return null;
					}
				}
			}
		}
		// 计数
		size --;
		return node.getData();
	}
	
	/**
	 * 链表反转
	 * 
	 * @return 新链表
	 * 
	 * @author 延晓磊
	 * @return 
	 * @return 
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public DoubleCircleLinkedList<E> reverse() {
		// 0-1个元素：无需反转
		if (size < 2) {
			return this;
		}
		// 首尾互换
		first = last;
		// 反向遍历
		LinkedNode<E> curr = last;
		for (int i = 1; i < size; i++) {
			// 上一个节点
			curr = curr.getPre();
			// 添加在尾部，循环关联头节点
			last.setNext(new LinkedNode<>(curr.getData(), first, last));
			// 尾节点后移
			last = last.getNext();
			first.setPre(last);
		}
		return this;
	}

	
}
